import netscape.security.UserTarget;

import java.util.Arrays;
import java.util.Stack;

public class Test {

    public static void main(String[] args) {

        Test test = new Test();
        int[] arr = {12,33,32,2,2,43,3,78,6,7,9,-12};

        int a = 10;
        double b = 3.14;
        double c = 'a'+a-b;

//        test.insertSort(arr);
//        test.shell(arr);
//        test.selectSort(arr);
//        test.heapSort(arr);
//        test.bubbleSort(arr);
//        test.quickSort(arr);
//        test.quickNor(arr);
        test.mergeSortNor(arr);

        System.out.println(Arrays.toString(arr));


    }

    /**
     * 时间复杂度： O(N^2)
     * 空间复杂度： O(1)
     * 稳定性： 稳定
     * @param arr
     */
    public void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > temp){
                    // 大于 temp，就向后移
                    arr[j+1] = arr[j];
                }else {
                    // 找到适合的位置，不用再往前找了，直接退出循环
                    break;
                }
            }
            //当回退到 -1 位置，进不了循环，不能给第一位赋值
            arr[j+1] = temp;
        }
    }

    /**
     * 时间复杂度： O(n^1.3 ~ n^1.5)
     * 空间复杂度： O(1)
     * 稳定性： 不稳定
     * @param arr
     */
    public void shell(int[] arr){
        int gap = arr.length;// 最大的组数
        while (gap > 1){
            // 传入每次的组数
            shell(arr,gap);
            // 这里的分组每次除以 2
            gap /= 2;
        }
        //最后看做一组进行排序
        shell(arr,1);
    }
    // 对分的组数进行直接插入排序
    public void shell(int[] arr,int gap){
        int right = gap;

        while (right < arr.length){
            int left = right - gap;
            int temp = arr[right];
            while (left >= 0){
                if (arr[left] > temp){
                    arr[left + gap] = arr[left];
                    left -= gap;
                }else {
                    break;
                }
            }
            arr[left + gap] = temp;
            right++;
        }
    }


    /**
     * 时间复杂度： O(n^2)
     * 空间复杂度： O(1)
     * 稳定性： 不稳定
     */
    public void selectSort(int[] arr){
        for (int start = 0; start < arr.length; start++) {
            int minIndex = start;
            for (int i = start+1; i < arr.length; i++) {
                // 找到最小值下标
                if (arr[minIndex] > arr[i]){
                    minIndex = i;
                }
            }
            // 交换无序区间第一个值和当前无序区间最小值
            int temp = arr[start];
            arr[start] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }


    /**
     * 时间复杂度： O(n * logN)
     * 空间复杂度： O(1)
     * 稳定性： 不稳定
     */
    public void heapSort(int[] arr){
        createHeap(arr);
        int end = arr.length-1;
        while (end > 0){
            // 交换最后一个位置和第一个位置上的值
            int temp = arr[end];
            arr[end] = arr[0];
            arr[0] = temp;
            // 向下调整变成大根堆
            shiftDown(arr,0,end);
            // end--
            end--;
        }
    }
    // 建立大根堆
    public void createHeap(int[] arr){
        // 得到最后一颗子树的根节点
        int parent = (arr.length-1-1)/2;
        // 向上调整直到来到根节点
        for (int i = parent; i >= 0; i--) {
            shiftDown(arr,i,arr.length);
        }
    }
    // 向下调整
    public void shiftDown(int[] arr,int parent,int end){
        int child = 2*parent+1;
        while (child < end){
            // 找到较大的孩子
            if (child+1 < end && arr[child] < arr[child+1]){
                child = child+1;
            }

            // 孩子更大，交换
            if (arr[parent] < arr[child]){
                int temp = arr[parent];
                arr[parent] = arr[child];
                arr[child] = temp;
                parent = child;
                child = 2*parent + 1;
            }else {
                // 不需要交换，直接退出
                break;
            }
        }
    }


    /**
     * 时间复杂度： O(n^2)
     * 空间复杂度： O(1)
     * 稳定性： 稳定
     */
    public void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            // 定义一个标志位，判断是否已经有序了
            // 若没有发生交换，则已经有序了，直接退出
            boolean flag = true;
            for (int j = 0; j < arr.length-1-i; j++) {
                // 当 j 大于 j+1，交换，将较大值换到后面去
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    flag = false;
                }
            }
            if (flag) {
                // 没发生过交换
                break;
            }
        }
    }


    public void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }

    /**
     * 时间复杂度： O(N * logN)
     * 空间复杂度： O(logN)
     * 稳定性： 不稳定
     */
    public void quick(int[] arr,int left,int right){

        // 终止条件： left >= right ,不需要对该区间进行排序了,已经有序或者没有数据
        if (left >= right) {
            return;
        }

        // 找到基准，并将 <= 基准值的放到基准值的左边，> 基准值的放到基准值的右边
        // 基准位置为 pivot
        int pivot = partition(arr,left,right);
        // 递归基准的左边子区间
        quick(arr,left,pivot-1);
        // 递归基准的右边子区间
        quick(arr,pivot+1,right);
    }
    // 找基准
    public int partition(int[] arr,int start,int end){
        int middle = findMiddle(arr,start,end);
        int temp = arr[start];
        arr[start] = arr[middle];
        arr[middle] = temp;

        temp = arr[start];
        while (start < end){
            while (start < end && arr[end] >= temp){
                end--;
            }
            // end找到小于 temp的值，填补空格
            arr[start] = arr[end];

            while (start < end && arr[start] <= temp){
                start++;
            }
            // start找到大于 temp的值，填补空格
            arr[end] = arr[start];
        }
        // 将temp的值给最后的空格, 即基准位置
        arr[start] = temp;
        return start;
    }
    // 找到三数的中间大小值
    public int findMiddle(int[] arr,int start,int end){
        int middle = start + ((end - start) >>> 1);

        int max = Math.max(arr[start],Math.max(arr[middle],arr[end]));
        int min = Math.min(arr[start],Math.min(arr[middle],arr[end]));

        if(start != max && start != min){
            return start;
        }else if(middle != max && middle != min){
            return middle;
        }else {
            return end;
        }
    }

    /**
     * 非递归实现快速排序
     */
    public void quickNor(int[] arr){

        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length-1;
        // 找到基准
        int pivot = partition(arr,left,right);

        // 左边区间至少有两个数，需要再排序
        if (pivot - 1 > left){
            // 放入左区间的左边边界点
            stack.push(left);
            // 放入左区间的右边边界点
            stack.push(pivot-1);
        }
        // 右边区间至少有两个数，需要再排序
        if (right - 1 > pivot){
            // 放入右区间的左边边界点
            stack.push(pivot+1);
            // 放入右区间的右边边界点
            stack.push(right);
        }

        while (!stack.isEmpty()){
            // 弹出两个元素作为一个区间
            right = stack.pop();
            left = stack.pop();

            // 找到基准
            pivot = partition(arr,left,right);

            // 左边区间至少有两个数，需要再排序
            if (pivot - 1 > left){
                // 放入左区间的左边边界点
                stack.push(left);
                // 放入左区间的右边边界点
                stack.push(pivot-1);
            }
            // 右边区间至少有两个数，需要再排序
            if (right - 1 > pivot){
                // 放入右区间的左边边界点
                stack.push(pivot+1);
                // 放入右区间的右边边界点
                stack.push(right);
            }
        }
    }

    /**
     * 归并排序
     */
    public void mergeSort(int[] arr){
//        mergeSortInternal(arr,0,arr.length-1);
    }
    public void mergeSortInternal(int[] arr,int left,int right){
        if (left >= right){
            return;
        }
        int middle = (left + right) >>> 1;
        // 递归左边
        mergeSortInternal(arr,left,middle);
        // 递归右边
        mergeSortInternal(arr,middle+1,right);
        // 归并
        merge(arr,left,middle,right);
    }
    public void merge(int[] arr,int left,int middle,int right){
        int s1 = left;
        int e1 = middle;
        int s2 = middle+1;
        int e2 = right;
        int[] temp = new int[right-left+1];
        int index =  0;

        while (s1 <= e1 || s2 <= e2){
            if (s1 <= e1 && s2 <= e2){
                if (arr[s1] <= arr[s2]){
                    temp[index++] = arr[s1++];
                }else {
                    temp[index++] = arr[s2++];
                }
            }else if (s1 <= e1){
                temp[index++] = arr[s1++];
            }else {
                temp[index++] = arr[s2++];
            }
        }

        // 将 temp数组拷贝到 arr的 left~right区间
        for (int i = 0; i < temp.length; i++) {
            arr[i + left] = temp[i];
        }
    }

    public void mergeSortNor(int[] arr){

        int gap = 2;// 初始每组两个数据
        while (gap <= arr.length*2){

            for (int left = 0; left < arr.length; left += gap) {

                // 找到 right 的位置，处理越界
                int right = (left + gap - 1 < arr.length) ? (left + gap - 1) : arr.length-1;
                // 找到 middle 的位置，处理越界
                int middle = (left + gap/2 - 1 < arr.length) ? (left + gap/2 - 1) : arr.length-1;
                // 合并当前区间
                merge(arr,left,middle,right);
            }
            gap *= 2;
        }
    }
}
